package DataStructure.priority;

public class IndexMaxPriorityQueue<T extends Comparable<T>> {
    private T[] items;
    private int[] pq;
    private int[] qp;
    private int N;

    public IndexMaxPriorityQueue(int capacity){
        this.items=(T[]) new Comparable[capacity+1];
        this.pq=new int[capacity+1];
        this.qp=new int[capacity+1];
        this.N=0;
        for (int i = 0; i < qp.length; i++) {
            qp[i]=-1;
        }
    }


    public int size(){
        return N;
    }

    public boolean isEmpty(){
        return N==0;
    }

    public boolean less(int i,int j){
        return items[pq[i]].compareTo(items[pq[j]])<0;
    }

    public void exch(int i,int j){
        int temp=pq[i];
        pq[i]=pq[j];
        pq[j]=temp;

        qp[pq[i]]=i;
        qp[pq[j]]=j;
    }

    //判断是否关联
    private boolean contains(int k){
        return qp[k]!=-1;
    }

    //最大元素关联的索引
    public int maxIndex(){
        return pq[1];
    }

    //插入一个元素并关联索引
    public void insert(int i,T t){
        if(contains(i)){
            return;
        }

        N++;
        items[i]=t;
        pq[N]=i;
        qp[i]=N;
        swim(N);
    }

    //删除最大元素并返回索引
    public int delMax(){
        int maxIndex=pq[1];
        exch(1,N);
        qp[pq[N]]=-1;
        pq[N]=-1;
        items[maxIndex]=null;
        N--;
        sink(1);
        return maxIndex;
    }

    //删除索引i处的值
    public void delete(int i){
        int k=qp[i];
        exch(k,N);
        qp[pq[N]]=-1;
        pq[N]=-1;
        items[i]=null;
        N--;
        swim(k);
        sink(k);
    }

    //改变i处的值
    public void changeItem(int i,T t){
        items[i]=t;
        int k=qp[i];
        swim(k);
        sink(k);
    }

    //上浮
    private void swim(int k){
        while (k>1){
            if(less(k/2,k)){
                exch(k,k/2);
            }
            k=k/2;
        }
    }
    private void sink(int k){
        while (2*k<=N){
            int max;
            if(2*k+1<=N){
                if(less(2*k,2*k+1)){
                    max=2*k+1;
                }else {
                    max=2*k;
                }
            }else {
                max=2*k;
            }

            if(less(max,k)){
                break;
            }
            exch(max,k);
            k=max;
        }
    }

}
